package com.qh.xx.链表;

/**
 * @description:
 * @author: zqh
 * @date: 2021/11/1 12:47
 * https://leetcode-cn.com/problems/linked-list-cycle/
 **/
public class _141_环形链表 {

    // * Definition for singly-linked list.
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 快慢指针思想
     * 快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。
     * 判断单链表是否为循环链表
     * 让快慢指针从链表头开始遍历，快指针向前移动两个位置，慢指针向前移动一个位置;如果快指针到达NULL，说明链表以NULL为结尾，不是循环链表。如果 快指针追上慢指针，则表示出现了循环。
     */
    public boolean hasCycle(ListNode head) {
        if (head ==null || head.next == null) {
            return false;
        }
        ListNode slow = head;//慢指针
        ListNode fast = head.next;//快指针
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast) {
                return true;
            }
        }
        return false;
    }
}
